package everydayGrade.t0;

/**
 * @Author: Siantar
 * @Date: 2023-11-26-16:54
 * @Description: 1.0
 */
public class T100135 {
    public int findMaximumLength(int[] nums) {
        int n = nums.length;
        long[] s = new long[n + 1];
        int[] f = new int[n + 1];
        long[] last = new long[n + 1];
        int[] q = new int[n + 1]; // 数组模拟队列
        int front = 0, rear = 0;
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1];

            // 去掉队首无用数据（计算转移直接取队首）
            while (front < rear && s[q[front + 1]] + last[q[front + 1]] <= s[i]) {
                front++;
            }

            // 计算转移
            f[i] = f[q[front]] + 1;
            last[i] = s[i] - s[q[front]];

            // 去掉队尾无用数据
            while (rear >= front && s[q[rear]] + last[q[rear]] >= s[i] + last[i]) {
                rear--;
            }
            q[++rear] = i;
        }
        return f[n];
    }
}
